package com.michael.leetcode;

import org.junit.Test;

public class RepeatedSubstringPattern_459 {

    /**
     *  459. 重复的子字符串
     * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
     *
     * 示例 1:
     * 输入: s = "abab"
     * 输出: true
     * 解释: 可由子串 "ab" 重复两次构成。
     *
     * 示例 2:
     * 输入: s = "aba"
     * 输出: false
     *
     * 示例 3:
     * 输入: s = "abcabcabcabc"
     * 输出: true
     * 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
     *
     *
     * 提示：
     * 1 <= s.length <= 104
     * s 由小写英文字母组成
     */
    public boolean repeatedSubstringPattern(String s) {
        for (int i = 1; i < s.length(); i++) {
            if (s.length() % i != 0) {
                continue;
            }
            String tag = s.substring(0, i);
            int cc = s.length() / i;
            StringBuilder sb = new StringBuilder();
            sb.append(tag.repeat(cc));

            if (sb.toString().equals(s)) {
                return true;
            }
        }
        return false;
    }


    @Test
    public void test(){
        String s = "abab";
        boolean b = repeatedSubstringPattern(s);

    }

    /**
     *
     *
     * 优化版
     */
    public boolean repeatedSubstringPatternV1(String s) {
        tt: for (int i = 1; i < s.length(); i++) {
            if (s.length() % i != 0) {
                continue;
            }
            String tag = s.substring(0, i);
            int cc = s.length() / i;
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cc ; j++) {
                sb.append(tag);

                String s1 = s.substring(0, tag.length()*j);
                if (!sb.toString().equals(s1)) {
                    continue tt;
                }


            }

            if (sb.toString().equals(s)) {
                return true;
            }
        }
        return false;
    }

}
